﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_104_MaxDepth
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class MainProject
    {
        static void Main(string[] args)
        {
            //[1,2,2,null,3,null,3]
            //TreeNode treeNode = new TreeNode(3, new TreeNode(1, null, null), new TreeNode(2, null, null));
            TreeNode treeNode = new TreeNode(1,new TreeNode(2,new TreeNode(3,new TreeNode(4,new TreeNode(5)))));
            Console.WriteLine(MaxDepth(treeNode));
            Console.ReadKey();
        }
        public static int MaxDepth(TreeNode root)
        {
            //深度优先算法  思路 左子树和右子树最大深度+1
            //if (root == null)
            //{
            //    return 0;
            //}
            //else
            //{
            //    int leftHeight = MaxDepth(root.left);
            //    int rightHeight = MaxDepth(root.right);
            //    return Math.Max(leftHeight, rightHeight) + 1;
            //}
            //广度优先算法
            if (root == null)
            {
                return 0;
            }
            Queue<TreeNode> que = new Queue<TreeNode>();
            que.Enqueue(root);
            int count = 0;
            while (que.Count>0)
            {
                int size = que.Count;
                while (size>0)
                {
                    TreeNode treeNode = que.Dequeue();
                    if (treeNode.left!=null)
                    {
                        que.Enqueue(treeNode.left);
                    }
                    if (treeNode.right != null)
                    {
                        que.Enqueue(treeNode.right);
                    }
                    size--;
                }
                count++;
            }
            return count;
        }
    }
}

